package com.wp.基本算法.排序;

import java.util.Arrays;

/**
 * Created by 王萍 on 2017/8/23 0023.
 */
//第一次：比较前两个数，进行排序
// 第二次：观察第三个数是否小于第二个数（此时第二个数是前两个数的最大值），若小于，则与第二个数进行交换。
// 再使用第二个数与第一个数比较。依次类推.......如insertSort2方法实现

//第二次：观察第三个数是否小于第二个数，若小于，本应该交换，但是这里先不交换，用变量tmp记录第三个数的值，并使array[2]=array[1],
// 再用tmp与第一个数比较，若tmp小于第一个数，则使array[1]=array[0]。此时无法继续向前比较，将tmp赋给array[0]。
//依次类推........如insertSort方法的实现。

//相对insertSort2来说，insertSort性能更好，少一些交换赋值操作。
public class 插入排序 {

    public static void main(String[] args) {

        Comparable[] numbers = new Comparable[]{2, 3, 5, 1, 4, 9, 6};
        insertSort(numbers);
        Arrays.stream(numbers).forEach(number -> System.out.print(number + " "));

        Comparable[] chars = new Comparable[]{'w', 'a', 'n', 'g', 'p', 'i', 'n', 'g'};
        insertSort2(chars);
        Arrays.stream(chars).forEach(number -> System.out.print(number + " "));
    }

    public static Comparable[] insertSort(Comparable[] array) {
        int length = array.length;
        Comparable tmp;
        for (int i = 1; i < length; i++) {
            if (array[i].compareTo(array[i - 1]) < 0) {
                tmp = array[i];
                int j = i;
                while (j > 0 && tmp.compareTo(array[j - 1]) < 0) {
                    array[j] = array[j - 1];
                    j--;
                }
                array[j] = tmp;
            }
        }
        return array;
    }

    public static Comparable[] insertSort2(Comparable[] array) {
        int length = array.length;
        Comparable tmp;
        for (int i = 1; i < length; i++) {
            int j = i;
            while (j > 0 && array[j].compareTo(array[j - 1]) < 0) {
                tmp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = tmp;
                j--;
            }
        }
        return array;
    }
}
